Machine readable symbologies are widely used for data collection. The first bar code symbologies developed, such as UPC, EAN, Code 39 and Code 93 can be referred to as "linear" symbologies because the data in a given symbol was decoded along one direction or axis. The next generation of bar code symbologies, called stacked reader symbologies, such as Code 49 and PDF 417, increase the information density of the symbol by employing several adjacent rows, each row having several symbol characters defined by groups of multiple width bars and spaces.
A recently developed symbology, Code One, is a two-dimensional matrix symbology. As shown by a symbol 800 of FIG. 1, Code One symbols include a recognition pattern 802, a matrix of square data cells 804, rather than one or more rows of bars and spaces, vertical reference patterns 806, which extend away from the recognition pattern 802. The areas of square data cells 804 above the recognition pattern 802, and below the recognition pattern 802, respectively, are defined by an upper bounding box 808 and a lower bounding box 809. The recognition pattern 802 runs horizontally through the Code One symbol 800, while the vertical reference patterns 806 extend perpendicularly from the recognition pattern 802. These vertical recognition patterns 806 are used to help find the symbology, and determine the symbology's tilt and orientation to take into account any surface curvature of the symbol 800.
Each of the data cells 804 in the matrix encodes one bit of data: a white data cell represents a 0 and a black data cell represents a 1. Each symbol character in the Code One symbology is generally constructed from eight data cells in a rectangular array of two rows that each have four data cells. Each set of eight data cells in a Code One symbol character encodes an 8-bit byte of binary data. The ASCII values in the Code One symbology are equal to the standard ASCII values in the computer industry plus one.
In a given Code One symbol, the symbol characters are ordered in a row-wise fashion from left to right, and the "rows" of symbol characters are arranged from top to bottom in the symbol. Each row of symbol characters in a Code One symbol consists of a pair of adjacent rows of data cells. The first symbol character in the Code One symbol is in the top left corner of the symbol and the last symbol character is in the bottom right corner. A reader analyzes the symbol characters in a Code One symbol from the first symbol character in the symbol's top left corner rightward to the right edge of the top row, and then from the left edge rightward along the second row, and so forth. Assuming the reader encounters no difficulties, each symbol character analyzed in a Code One or other symbology is converted into corresponding data to be used by the reader, the user, or other peripheral equipment.
The recognition pattern 802 is comprised of a plurality of elements including bars 810 and spaces 812. The recognition pattern 802 is used to identify the version (i.e., the type) of Code One symbol being used. Further, the recognition pattern 802 is used to determine the X-dimension of the Code One symbol 800. For example, the X-dimension represents the smallest height (or width) of the data cells 804 in the Code One symbology. The X-dimension is used to determine the intended dimension that an area symbology is based on, regardless of printing errors, and is necessary for decoding the symbology.
The reader used to scan the Code One symbol 800 is a two-dimensional imaging device which detects all the spaces 810 and the bars 812 of the recognition pattern 802, as well as the vertical reference patterns 806 using a fast linear image search routine used in high-speed scanning applications. A memory stores the scanned image and includes an array of memory locations that correspond to and represent a pixel field of view of the reader (e.g., a rectangular array of 582 by 752 pixels). The stored image is referenced by a Cartesian coordinate system relative to the imaging device or memory so that the location of each pixel is represented by a pair of numbers indicating the horizontal and vertical position of the pixel in the stored image. For example, the first pixel in the top left corner of the stored image is assigned the Cartesian coordinates (0,0) while the bottom right-most pixel is assigned the coordinates (752,582). Therefore, data cells 804 associated with groups of pixels can be arithmetically located using known geometric and trigonometric properties based on the coordinate system.
In the prior art, as shown in FIG. 2, to determine the location of all the data cells 804 within the stored image, the image search routine was used to locate a long bar 814 of the recognition pattern 802, then the X-dimension was determined from the recognition pattern 802. Next, an angle 816 that the long bar 814 makes with the X axis of the Cartesian coordinate system of the overall image was determined. Finally, using the above X-dimension and angle 816, a bounding box 807 of the symbol 800 defined by the boundary lines of the symbol 800 was determined.
The prior method computes one bounding box 807 for the Code One symbol 800 enclosing the entire symbol 800. The boundary box 807 is the sum of upper bounding box 808, lower bounding box 809 and the center pattern recognition 802. To determine the size and location of the bounding box 807, an end point 818 of the long bar 814, i.e., ep.sub.1, was located and a path 820, substantially along the Y-axis of the Cartesian coordinate system, i.e., directed away from the recognition pattern 802, was traversed for a predetermined number of the X-dimensions. The direction of the path 820 was determined by the angle that is vertical to the long bar 814 (i.e., the angle 816) to establish an end corner point cp.sub.1 824 of the bounding box 807. The other corner point 828, i.e., cp.sub.2, of the bounding box 807, and the other corner points 842 and 844, i.e., cp.sub.3 and cp.sub.4, of the bounding box 807 were determined in a similar manner. With these corner points, the complete bounding box 807 was defined, and all square data cells 804 were assumed to lie within this region for purposes of information retrieval from the image when the size of the X-dimension and the version of the symbol were known.
Although the prior art method of determining the bounding box 807 of the Code One symbol is effective when the symbol 800 is in its proper position, and has no significant surface curvature, it becomes highly prone to errors when the symbology 800 is optically distorted, e.g., when an image of the symbol is stored when a reader is significantly tilted with respect to the symbol. In other words, when the upper and lower bounding boxes 808 and 809 do not have the same size and shape, and the X-dimension varies within the symbol, data can be lost during the decoding process.
For example, as shown by an optically distorted symbol 800' in FIG. 3, even a slight deviation between the angle the long bar 814 makes with an X axis of the Cartesian coordinate system causes the computed bounding box 807 defined by the dashed boundaries with four corners cp1, cp2, cp3, and cp4 to differ from the true bounding box for the symbol (shown as the solid line quadrilateral 830). Additionally, optical distortions causing the stored image of the symbol to appear trapezoidal or otherwise optically distorted, as shown in FIG. 3, causes the perimeter of the stored image of the symbol 830 to differ significantly from the bounding box 807 computed by the prior art method. As a result, information retrieval errors will result by sampling within the computed bounding box 807. Important data within the true bounding box 830 can be ignored, such as the information located in shaded areas 837 of FIG. 3. This is because when following an angle that has a slight error, the resulting positional error can be huge if the distance along the path is large enough. In other words, the error will accumulate to a significant degree using the prior art method, even if only a small amount of error is present in the direction of the path. Similarly, when there is a slight error in X-dimension, the total error will be larger if the distance is large enough. Thus, what is needed is a method of determining the bounding box that localized the data region and is free from error, and which will ensure that all the square data cells 804 fall within the true bounding box.